/**
 * Created by L.jp
 * Description:在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
 * 例如，链表 1->2->3->3->4->4->5  处理后为 1->2->5
 * User: 86189
 * Date: 2022-02-12
 * Time: 23:25
 */
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
       //这种需要返回新的头结点题目，需要创建一个虚拟的头节点，让虚拟节点连接原来的头结点
        //删除所有重复的节点，那么就需要一个前驱节点去记录最后一个没有重复的节点，然后一个cur去遍历链表，
        // 遇到重复的就跳过，找到不重复的就把上次最后一个不重复的节点的后继连接到下一个不重复的节点，
        // 如果后面还有重复的，那么就再把不重复节点的后继连接到下一个没有重复的节点
        ListNode newHead = new ListNode(0);//虚拟节点
        newHead.next=pHead;
        ListNode prev=newHead;//前驱节点，记录不重复节点位置
        ListNode cur=pHead;//搜索待删除节点
        //遍历链表
        while (cur!=null){
            //如果当前节点值不等于下一个节点的值
            if(cur.next==null || cur.val!=cur.next.val){ //cur.next==null保证在遍历到最后一个节点时，此时cur在最后一个节点，就需要让cur为空，才能跳出循环，所以要加上cur==null这个条件
                //那么就不用删，往后走
                prev=prev.next;
                cur = cur.next;
            }else{
                //如果当前节点的值等于下一个节点的值，就要找到不重复的下一个节点
                while(cur.next!=null && cur.val==cur.next.val){
                    //让它继续遍历，直到找到不重复节点为止
                    cur = cur.next;
                }
                //找到了下一个不重复的节点，但是prev不着急跳过来，因为prev位置必须是不重复节点，但是此时还不一定当前节点是不重复的，所以需要先判断
                //可以先把前驱节点的后继连接过来，但是前驱节点没那么快过来
                //此时找到了一个不重复节点，说明当前节点的下一个节点是不重复的，可以把前驱节点的后继连过来
                prev.next = cur.next;
                //继续搜索待删除节点
                cur = cur.next;
            }
        }
        return newHead.next;//虚拟节点的下一个节点就是新链表头结点
    }

}
